package src.BlueBridge.GreedyStrategyAndDynamicProgramming;

/**
    最长递增子序列的长度
    输入4 2 3 1 5
    输出3 (因为2 3 5组成了最长递增子序列)
 */

public class _14最长上升子序列 {
    static int[] arr = new int[]{4, 2, 3, 1, 5, 6};
    public static void main(String[] args) {
        System.out.println(f(arr));
        System.out.println(dp(arr));
        System.out.println(dp1(arr));
    }

    /**
     * 暴力破解
     * @param arr
     * @return
     */
    public static int f(int[] arr) {
        int maxCount = 0;
        // 每一个都可能会打头，所以要循环每一个都尝试一下
        for (int i = 0 ; i < arr.length ; i++) {
            // 使用一个指针来记录现在的最大值
            int p = i;
            // 计数
            int count = 1;
            // 要从它的后面去找
            for (int j = i + 1 ; j < arr.length ; j++) {
                if (arr[j] > arr[p]) {
                    // 计数加一
                    count++;
                    // 指针重置
                    p = j;
                }
            }
            // 更新最大长度
            if (count > maxCount) {
                maxCount = count;
            }
        }
        return maxCount;
    }

    /**
     * 动态规划算法
     * @param arr
     * @return
     */
    static int[] dp = new int[arr.length + 1];
    public static int dp(int[] arr) {
        // 第一位肯定是1，因为只有一个元素
        dp[0] = 1;
        for (int i = 1 ; i < arr.length ; i++) {// i是定下的目标
            // 计数器
            int count = 1;
            for (int j = i - 1 ; j >= 0 ; j--) {// j是待比较的元素
                if (arr[i] > arr[j]) {
                    count = Math.max(count, dp[j] + 1);
                }
            }
            // 将真正的值赋给每个位
            dp[i] = count;
        }
        int answer = -1;
        for (int i = 0 ; i < dp.length ; i++) {
            answer = Math.max(answer, dp[i]);
        }
        return answer;
    }

    /**
     * 巧妙dp
     * @param arr
     * @return
     */
    public static int dp1(int[] arr) {
        dp = new int[arr.length + 1];
        // 长度为1的最长递增子序列，初始化为第一个元素
        dp[1] = arr[0];
        // 指针，记录dp更新的最后位置
        int p = 1;
        for (int i = 1 ; i < arr.length ; i++) {
            if (arr[i] > dp[p]) {
                dp[p + 1] = arr[i];
                p++;
            }else {// 扫描dp数组，替换掉第一个比他大的元素
//                for (int j = 0 ; j <= p ; j++) {
//                    if (dp[j] > arr[j]) {
//                        dp[j] = arr[i];
//                    }
//                }

                // 这里可以用二分法优化
                int indexOfFirstBigger = indexOfFirstBigger(dp, arr[i], 0, p);
                if (indexOfFirstBigger != -1) {
                    dp[indexOfFirstBigger] = arr[i];
                }
            }
        }
        return p;
    }

    public static int indexOfFirstBigger(int[] dp, int v, int l, int r) {
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (dp[mid] > v) {
                // 保留大于v的下标以防这是第一个
                r = mid;
            }else {
                l = mid + 1;
            }
            if (l == r && dp[l] > v)
                return l;
        }
        return -1;
    }
}
